package main

import (
	"fmt"
	"time"
)

// 暴力递归
func getValue(weights []int, values []int, idx int, limit int) int {
	if idx == len(values) || limit <= 0 {
		return 0
	}
	
	p1 := getValue(weights, values, idx + 1, limit)
	p2 := -1
	if weights[idx] <= limit {
		p2 = values[idx] + 
			getValue(weights, values, idx + 1, limit - weights[idx])
	}
	
	if p1 < p2 {
		return p2
	} else {
		return p1
	}
}

// 动态规划
func getValueCache(weights []int, values []int, idx int, limit int) int {
	if idx == len(values) || limit <= 0 {
		return 0
	}

	// var dp [len(values) + 1][limit + 1]int
	var dp [][]int
	for i := 0; i < len(values) + 1; i++ {
		arr := make([]int, limit+1)
		dp = append(dp, arr)
	} 

	var p1, p2 int
	for i := len(values) - 1; i >= 0; i-- {
		for j := 0; j < limit + 1; j++ {

			p1 = dp[i + 1][j]
			p2 = -1
			if weights[i] <= j {
				p2 = values[i] + dp[i + 1][j - weights[i]]
			}

			if p1 < p2 {
				dp[i][j] = p2
			} else {
				dp[i][j] = p1
			}
		}
	}
	
	// fmt.Println(dp)
	return dp[0][limit]
}

func main() {
	weights := []int{ 3, 2, 4, 7, 10, 7, 3, 2, 4, 7, 10, 7 }
	values := []int{ 5, 6, 3, 19, 11, 19, 11, 11, 19, 3, 6, 5 }
	go.bag := 23

	t1 := time.Now()
	v := getValue(weights, values, 0, go.bag)
	for i := 0; i < 100000; i++ {
		getValue(weights, values, 0, go.bag)
	}
	elapsed := time.Since(t1)
	fmt.Println(v)
	fmt.Println(elapsed)
}